#ifndef __GLF_CORE_COMPRESSION_H_INCLUDED__
#define __GLF_CORE_COMPRESSION_H_INCLUDED__

#include <glf/core/types.h>

namespace glf {

//! RunLengthEncoding

//! Compress a bit array by counting successive false bits:
//! - one byte is used to encode a count < 255
//! - three bytes are used to encode a count >= 255
//! - as an option, the false bit counter could be increased by 1 to avoid 0 value in sequence,
//!   thus allowing to use 0 value to specify an end of buffer
//! Max bit array size of 65536.

template <bool ZERO_FREE_OPTION, int TRUE_BIT_VALUE = true>
class RunLengthEncoding
{
public:

	//! Get the maximum size (in bytes) for the buffer needed 
	//! to encode a bit array of "bitCount" bits.
	template <typename BIT_ARRAY>
	static size_t getEncodedMaxSize(
		const BIT_ARRAY& /*bitArray*/, 
		unsigned short bitCount)
	{
		return bitCount;
	}

	//! Get the exact size (in bytes) for the buffer needed 
	//! to encode a bit array of "bitCount" bits.
	//! This method is slower than getEncodedMaxSize.
	template <typename BIT_ARRAY>
	static size_t getEncodedSize(
		const BIT_ARRAY& bitArray, 
		unsigned short bitCount);

	//! Get the exact size (in bytes) for the buffer needed 
	//! to encode a bit array of "bitCount" bits.
	//! This method is slower than getEncodedMaxSize.
	template <typename BIT_ARRAY_CONST_ITERATOR>
	static size_t getEncodedSize(
		BIT_ARRAY_CONST_ITERATOR bitArrayBegin, 
		BIT_ARRAY_CONST_ITERATOR bitArrayEnd);

	//! Get the maximum count of values (indexes of true bits) needed
	//! to decode an encoded buffer.	
	static unsigned short getDecodedMaxValueCount(
		size_t dataSize)
	{
		return dataSize;
	}

	//! Get the exact count of values (indexes of true bits) needed
	//! to decode an encoded buffer.
	//! This method is slower than getDecodedMaxValueCount.
	template <typename DATA_CONST_ITERATOR>
	static unsigned short getDecodedValueCount(
		DATA_CONST_ITERATOR dataBegin,
		DATA_CONST_ITERATOR dataEnd);
	
	//! Encode a bit array and return buffer size.
	template <typename DATA_ITERATOR, typename BIT_ARRAY>
	static size_t encode(
		DATA_ITERATOR dataBegin,
		DATA_ITERATOR dataEnd,
		const BIT_ARRAY& bitArray, 
		unsigned short bitCount);

	//! Encode a bit array and return buffer size.
	template <typename DATA_ITERATOR, typename BIT_ARRAY_CONST_ITERATOR>
	static size_t encode(
		DATA_ITERATOR dataBegin,
		DATA_ITERATOR dataEnd,
		BIT_ARRAY_CONST_ITERATOR bitArrayBegin, 
		BIT_ARRAY_CONST_ITERATOR bitArrayEnd);
	
	//! Decode an encoded buffer and return value count.
	template <typename VALUE_ITERATOR, typename DATA_CONST_ITERATOR>
	static unsigned short decode(
		VALUE_ITERATOR valueBegin,
		VALUE_ITERATOR valueEnd,
		DATA_CONST_ITERATOR dataBegin,
		DATA_CONST_ITERATOR dataEnd);

	//! Decode a zero terminated encoded buffer and return value count.
	template <typename VALUE_ITERATOR, typename DATA_CONST_ITERATOR>
	static unsigned short decode(
		VALUE_ITERATOR valueBegin,
		VALUE_ITERATOR valueEnd,
		DATA_CONST_ITERATOR dataBegin);
};

typedef RunLengthEncoding<true> RLE;

// RunLengthEncoding implementation

template <bool ZERO_FREE_OPTION, int TRUE_BIT_VALUE>
template <typename BIT_ARRAY>
size_t RunLengthEncoding<ZERO_FREE_OPTION, TRUE_BIT_VALUE>::getEncodedSize(const BIT_ARRAY& bitArray, 
																		   unsigned short bitCount)
{
	size_t size = 0;
	unsigned short zeroCount = ZERO_FREE_OPTION ? 1 : 0;
	for (int i = 0; i < bitCount; ++i) {
		const bool trueBit = (int)bitArray[i] == TRUE_BIT_VALUE;
		size += trueBit ? (zeroCount < 255 ? 1 : 3) : 0;
		zeroCount = trueBit ? (ZERO_FREE_OPTION ? 1 : 0) : zeroCount + 1;
	}
	return size;
}

template <bool ZERO_FREE_OPTION, int TRUE_BIT_VALUE>
template <typename BIT_ARRAY_CONST_ITERATOR>
size_t RunLengthEncoding<ZERO_FREE_OPTION, TRUE_BIT_VALUE>::getEncodedSize(BIT_ARRAY_CONST_ITERATOR bitArrayBegin, 
																		   BIT_ARRAY_CONST_ITERATOR bitArrayEnd)
{
	size_t size = 0;
	unsigned short zeroCount = ZERO_FREE_OPTION ? 1 : 0;
	for (BIT_ARRAY_CONST_ITERATOR bitArrayIt = bitArrayBegin; bitArrayIt != bitArrayEnd; ++bitArrayIt) {
		size += (int)*bitArrayIt == TRUE_BIT_VALUE ? (zeroCount < 255 ? 1 : 3) : 0;
		zeroCount = (int)*bitArrayIt == TRUE_BIT_VALUE ? (ZERO_FREE_OPTION ? 1 : 0) : zeroCount + 1;
	}
	return size;
}

template <bool ZERO_FREE_OPTION, int TRUE_BIT_VALUE>
template <typename DATA_ITERATOR, typename BIT_ARRAY>
size_t RunLengthEncoding<ZERO_FREE_OPTION, TRUE_BIT_VALUE>::encode(DATA_ITERATOR dataBegin,
																   DATA_ITERATOR dataEnd,
																   const BIT_ARRAY& bitArray, 
																   unsigned short bitCount)
{
	GLF_ASSERT(dataEnd - dataBegin >= (int)getEncodedSize(bitArray, bitCount));
	DATA_ITERATOR data = dataBegin;	
	unsigned short zeroCount = ZERO_FREE_OPTION ? 1 : 0;
	for (int i = 0; i < bitCount; ++i) {
		if ((int)bitArray[i] == TRUE_BIT_VALUE) {
			if (zeroCount < 255)
				*(data++) = (unsigned char)zeroCount;
			else {
				*(data++) = 255;
				*(data++) = zeroCount & 0xFF;
				*(data++) = (zeroCount >> 8) & 0xFF;
			}
			zeroCount = ZERO_FREE_OPTION ? 1 : 0;
		}
		else
			++zeroCount;
	}
	GLF_ASSERT(data - dataBegin <= dataEnd - dataBegin);
	return data - dataBegin;
}

template <bool ZERO_FREE_OPTION, int TRUE_BIT_VALUE>
template <typename DATA_ITERATOR, typename BIT_ARRAY_CONST_ITERATOR>
size_t RunLengthEncoding<ZERO_FREE_OPTION, TRUE_BIT_VALUE>::encode(DATA_ITERATOR dataBegin,
																   DATA_ITERATOR dataEnd,
																   BIT_ARRAY_CONST_ITERATOR bitArrayBegin, 
																   BIT_ARRAY_CONST_ITERATOR bitArrayEnd)
{
	GLF_ASSERT(dataEnd - dataBegin >= (int)getEncodedSize(bitArrayBegin, bitArrayEnd));
	DATA_ITERATOR data = dataBegin;	
	unsigned short zeroCount = ZERO_FREE_OPTION ? 1 : 0;
	for (BIT_ARRAY_CONST_ITERATOR bitArrayIt = bitArrayBegin; bitArrayIt != bitArrayEnd; ++bitArrayIt) {
		if ((int)*bitArrayIt == TRUE_BIT_VALUE) {
			if (zeroCount < 255)
				*(data++) = (unsigned char)zeroCount;
			else {
				*(data++) = 255;
				*(data++) = zeroCount & 0xFF;
				*(data++) = (zeroCount >> 8) & 0xFF;
			}
			zeroCount = ZERO_FREE_OPTION ? 1 : 0;
		}
		else
			++zeroCount;
	}
	GLF_ASSERT(data - dataBegin <= dataEnd - dataBegin);
	return data - dataBegin;
}

template <bool ZERO_FREE_OPTION, int TRUE_BIT_VALUE>
template <typename DATA_CONST_ITERATOR>
unsigned short RunLengthEncoding<ZERO_FREE_OPTION, TRUE_BIT_VALUE>::getDecodedValueCount(DATA_CONST_ITERATOR dataBegin,
																						 DATA_CONST_ITERATOR dataEnd)
{
	unsigned short valueCount = 0;
	for (
		DATA_CONST_ITERATOR data = dataBegin; 
		data != dataEnd; 
		data += *data == 255 ? 3 : 1, ++valueCount);
	return valueCount;
}

template <bool ZERO_FREE_OPTION, int TRUE_BIT_VALUE>
template <typename VALUE_ITERATOR, typename DATA_CONST_ITERATOR>
unsigned short RunLengthEncoding<ZERO_FREE_OPTION, TRUE_BIT_VALUE>::decode(VALUE_ITERATOR valueBegin,
																		   VALUE_ITERATOR valueEnd,
																		   DATA_CONST_ITERATOR dataBegin,
																		   DATA_CONST_ITERATOR dataEnd)
{
	GLF_ASSERT(valueEnd - valueBegin >= getDecodedMaxValueCount(dataEnd - dataBegin));
	VALUE_ITERATOR value = valueBegin;
	unsigned short offset = ZERO_FREE_OPTION ? (unsigned short)-1 : 0;
	for (DATA_CONST_ITERATOR data = dataBegin; data != dataEnd; ++data) {
		if (*data == 255) {
			const unsigned char v0 = *(++data);
			const unsigned char v1 = *(++data);
			offset += v0 | (v1 << 8);
		}
		else
			offset += *data;			
		*(value++) = offset;
		offset += ZERO_FREE_OPTION ? 0 : 1;
	}
	GLF_ASSERT(value - valueBegin <= valueEnd - valueBegin);
	return value - valueBegin;
}

template <bool ZERO_FREE_OPTION, int TRUE_BIT_VALUE>
template <typename VALUE_ITERATOR, typename DATA_CONST_ITERATOR>
unsigned short RunLengthEncoding<ZERO_FREE_OPTION, TRUE_BIT_VALUE>::decode(VALUE_ITERATOR valueBegin,
																		   VALUE_ITERATOR valueEnd,
																		   DATA_CONST_ITERATOR dataBegin)
{
	if (!ZERO_FREE_OPTION)
	{
		GLF_ASSERT(!"Bad usage");
		return 0;
	}
	VALUE_ITERATOR value = valueBegin;
	unsigned short offset = ZERO_FREE_OPTION ? (unsigned short)-1 : 0;
	for (DATA_CONST_ITERATOR data = dataBegin; *data; ++data) {
		if (*data == 255) {
			const unsigned char v0 = *(++data);
			const unsigned char v1 = *(++data);
			offset += v0 | (v1 << 8);
		}
		else
			offset += *data;			
		*(value++) = offset;
		offset += ZERO_FREE_OPTION ? 0 : 1;
	}
	GLF_ASSERT(value - valueBegin <= valueEnd - valueBegin);
	return value - valueBegin;
}

} //namespace glf

#endif // __GLF_CORE_COMPRESSION_H_INCLUDED__
